package com.adamjwh.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 基数排序
 * 
 * @author adamjwh
 * 
 * 算法描述：
 * 取得数组中的最大数，并取得位数；
 * arr为原始数组，从最低位开始取每个位组成radix数组；
 * 对radix进行计数排序（利用计数排序适用于小范围数的特点）；
 *
 */
public class RadixSort {

	public static void radixSort(int[] arr, int d) {	//d为桶数（10进制范围0~9即10个桶）
		int max = arr[0];
		for (int i=0; i<arr.length; i++) {	//找出数组中的最大值
			max = Math.max(max, arr[i]);
		}
		
		int key = 0;	//数组中关键字的个数（以个位、十位、百位……为关键字，最大值的位数就是关键字的个数）
		while (max > 0) {
			max /= 10;
			key ++;
		}
		
		List<ArrayList<Integer>> buckets = new ArrayList<>();
		for (int i=0; i<d; i++) {
			buckets.add(new ArrayList<>());
		}
		
		for (int i=0; i<key; i++) {		//由个位开始，依次按关键字进行分配
			for (int j=0; j<arr.length; j++) {	//扫描所有元素，将其分配到桶
				int index = arr[j] % (int)Math.pow(10, i+1) / (int)Math.pow(10, i);		//取出个位、十位、百位……的数字
				buckets.get(index).add(arr[j]);
			}
			 
			//分配完成，将桶中元素复制回原数组
			int counter = 0;
			for (int j=0; j<10; j++) {
				ArrayList<Integer> bucket = buckets.get(j);	//关键字为j的桶
				while (bucket.size() > 0) {
					arr[counter++] = bucket.remove(0);
				}
			}
		}
		
	}
	
	//测试
	public static void main(String[] args) {
	    int[] arr = {1,9,3,12,7,8,3,4,65,22};

	    radixSort(arr, 10);

	    System.out.println(Arrays.toString(arr));
	}
	
}
